home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / C / ESPRESSO.ZIP / EXPAND.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-03-14  |  17.3 KB  |  522 lines
  1. /*
  2.     module: expand.c
  3.     purpose: Perform the Espresso-II Expansion Step
  4.  
  5.     The idea is to take each nonprime cube of the on-set and expand it
  6.     into a prime implicant such that we can cover as many other cubes
  7.     of the on-set.  If no cube of the on-set can be covered, then we
  8.     expand each cube into a large prime implicant by transforming the
  9.     problem into a minimum covering problem which is solved by the
  10.     heuristics of minimum_cover.
  11.  
  12.     These routines revolve around having a representation of the
  13.     OFF-set.  (In contrast to the Espresso-II manuscript, we do NOT
  14.     require an "unwrapped" version of the OFF-set).  The main idea is
  15.     the concept of distance between two cubes extended to the general
  16.     multiple-valued case (and the output part is treated as a multiple-
  17.     valued input).
  18. */
  19.  
  20. #include "espresso.h"
  21. #define HACK
  22.  
  23. static int num_covered;
  24. static pcube ESSEN_LOWER, LOWER, RAISE, XFREE, INIT_LOWER;
  25. static pcover BB, CC;
  26. /*
  27.     expand -- expand each nonprime cube of F into a prime implicant
  28.  
  29.     If gasp is true, a cube is saved only if it expands to cover another
  30.     cube; if it cannot cover another cube, expansion is stopped and the
  31.     cube is not returned in the result
  32.  
  33.     If nonsparse is true, only the non-sparse variables will be expanded;
  34.     this is done by forcing all of the sparse variables into the lowering
  35.     set.
  36. */
  37.  
  38. pcover expand(F, R, gasp, nonsparse)
  39. INOUT pcover F;
  40. IN pcover R;
  41. IN bool gasp;                   /* perform gasp expansion strategy */
  42. IN bool nonsparse;              /* expand non-sparse variables only */
  43. {
  44.     int var;
  45.     bool change;
  46.     register pcube last, p;
  47.  
  48.     /* Order the cubes according to "chewing-away from the edges" of mini */
  49.     F = mini_order(F, ascend);
  50.  
  51.     /* Setup the global variables for these routines */
  52.     ESSEN_LOWER = new_cube(); INIT_LOWER = new_cube();
  53.     LOWER = new_cube(); XFREE = new_cube();
  54.     BB = R; CC = F;
  55.  
  56.     /* Setup the initial lowering set (differs for nonsparse) */
  57.     (void) set_copy(INIT_LOWER, cube.emptyset);
  58.     if (nonsparse)
  59.         for(var = 0; var < cube.num_vars; var++)
  60.             if (cube.sparse[var])
  61.                 (void) set_or(INIT_LOWER, INIT_LOWER, cube.var_mask[var]);
  62.  
  63.     /* Mark all cubes as not covered, and maybe essential */
  64.     foreach_set(F, last, p)
  65.         RESET(p, COVERED), RESET(p, NONESSEN);
  66.  
  67.     /* Try to expand each nonprime and noncovered cube */
  68.     foreach_set(F, last, p)
  69.         /* do not expand if PRIME or (COVERED and not gasp) */
  70.         if (! (TESTP(p, PRIME) || (! gasp && TESTP(p, COVERED)))) {
  71.             expand1(p, gasp);
  72.             if (debug & EXPAND)
  73.                 printf("EXPAND: %s (covered %d)\n", pc1(p), num_covered);
  74.  
  75.             /* See if any cubes were covered */
  76.             if (num_covered == 0) {
  77.                 /* If gasping, don't save it (it didn't cover anything) */
  78.                 if (gasp)
  79.                     SET(p, COVERED);
  80.                 /* If not equal to overexpanded cube than nonessential */
  81.                 if (! setp_equal(LOWER, ESSEN_LOWER))
  82.                     SET(p, NONESSEN);
  83.             }
  84.         }
  85.  
  86.     /* Delete any cubes of F which became covered during the expansion */
  87.     F->active_count = 0;
  88.     change = FALSE;
  89.     foreach_set(F, last, p)
  90.         if (TESTP(p, COVERED)) {
  91.             RESET(p, ACTIVE);
  92.             change = TRUE;
  93.         } else {
  94.             SET(p, ACTIVE);
  95.             F->active_count++;
  96.         }
  97.     if (change)
  98.         F = sf_inactive(F);
  99.     free_cube(ESSEN_LOWER); free_cube(LOWER);
  100.     free_cube(XFREE); free_cube(INIT_LOWER);
  101.     return F;
  102. }
  103. /*
  104.     expand1 -- Expand a single cube against the OFF-set
  105. */
  106. void expand1(c, gasp)
  107. INOUT pcube c;
  108. IN bool gasp;
  109. {
  110.     int bestindex;
  111.  
  112.     if (debug & EXPAND1)
  113.         printf("\nEXPAND1: cube is %s\n", pc1(c));
  114.  
  115.     /* Initialize the lowering, raising and unassigned sets */
  116.     RAISE = c;
  117.     if (! setp_empty(set_copy(LOWER, INIT_LOWER))) {
  118.         (void) set_diff(LOWER, LOWER, c);
  119.         elim_lowering();
  120.     }
  121.     set_diff(XFREE, cube.fullset, set_or(XFREE, RAISE, LOWER));
  122.  
  123.     /* initialize BB, and CC */
  124.     SET(c, PRIME);
  125.     setup_BB_CC();
  126.     num_covered = 0;
  127.  
  128.     /* Determine what can and can't be raised, and save the lowering set */
  129.     (void) set_copy(ESSEN_LOWER, essen_parts());
  130.  
  131.     /* While there are still cubes which can be covered, cover them ! */
  132.     while (select_feasible() != (pcube) NULL)
  133.         (void) essen_parts();
  134.     if (gasp && num_covered == 0)
  135.         return;         /* quit early if unsuccessful gasp expansion */
  136.  
  137.     /* While there are still cubes covered by the overexpanded cube ... */
  138.     while (CC->active_count > 0) {
  139.         bestindex = most_frequent();
  140.         (void) set_insert(RAISE, bestindex);
  141.         (void) set_diff(XFREE, XFREE, RAISE);
  142.         (void) essen_parts();
  143.     }
  144.  
  145.     /* Finally, when all else fails, choose the largest possible prime */
  146.     while (BB->active_count > 0)
  147.         mincov();
  148. }
  149. /*
  150.     essen_parts -- determine which parts are forced into the lowering
  151.     set to insure that the cube be orthognal to the OFF-set.
  152.  
  153.     General rule: if any cube of the OFF-set is distance 1 from the
  154.     raising cube, then we must lower all parts of the conflicting
  155.     variable.  (If the cube is distance 0, we detect this error here.)
  156.  
  157.     If there are essentially lowered parts, we can remove from consideration
  158.     any cubes of the OFF-set which are more than distance 1 from the 
  159.     overexpanded cube of RAISE.
  160.  
  161.     After eliminating any such cubes of the off-set, we may then have
  162.     essentially raised parts which can be automatically added to the
  163.     raising set.
  164. */
  165. pset essen_parts()
  166. {
  167.     register pcube last, p, xlower = cube.temp[0];
  168.  
  169.     (void) set_copy(xlower, cube.emptyset);
  170.     foreach_active_set(BB, last, p)
  171.         switch (cdist01(p, RAISE)) {
  172.             case 0:
  173.                 fatal("espresso: ON-set and OFF-set are not orthogonal");
  174.             case 1:
  175.                 (void) force_lower(xlower, p, RAISE);
  176.                 BB->active_count--;
  177.                 RESET(p, ACTIVE);
  178.         }
  179.     if (debug & EXPAND1)
  180.         printf("ESSEN_LOWERING: xlower is: %s\n", pc1(xlower));
  181.  
  182.     (void) set_or(LOWER, LOWER, xlower);        /* add to lowering set */
  183.     (void) set_diff(XFREE, XFREE, xlower);      /* remove from free set */
  184.  
  185.     if (! setp_empty(xlower)) {
  186.         elim_lowering();
  187.         essen_raising();
  188.     }
  189.     return xlower;
  190. }
  191.  
  192.  
  193. /*
  194.     essen_raising -- determine which parts may always be added to
  195.     the raising set without restricting further expansions
  196.  
  197.     General rule: if some part is not blocked by any cube of BB, then
  198.     this part can always be raised.
  199. */
  200. void essen_raising()
  201. {
  202.     register pcube last, p, xraise = cube.temp[1];
  203.  
  204.     /* Form union of all cubes of BB, and then take complement wrt XFREE */
  205.     INLINEset_copy(xraise, cube.emptyset);
  206.     foreach_active_set(BB, last, p)
  207.         INLINEset_or(xraise, xraise, p);
  208.     INLINEset_diff(xraise, XFREE, xraise);
  209.     if (debug & EXPAND1)
  210.         printf("ESSEN_RAISING: xraise is: %s\n", pc1(xraise));
  211.  
  212.     INLINEset_or(RAISE, RAISE, xraise);         /* add to raising set */
  213.     INLINEset_diff(XFREE, XFREE, xraise);       /* remove from free set */
  214. }
  215. /*
  216.     elim_lowering -- after adding parts to the lowering set (LOWER), we
  217.     can reduce the size of both BB and CC.  BB can be reduced by those
  218.     cubes of the off-set which are orthogonal to the expanding cube, and
  219.     CC can be reduced by those cubes of the on-set which cannot be covered
  220.     by the expanding cube.
  221. */
  222. void elim_lowering()
  223. {
  224.     register pcube p, praise = cube.temp[2];
  225.     pcube last;
  226.  
  227.     /* Potentially raised set (raising all remaining free coordinates) */
  228.     INLINEset_or(praise, RAISE, XFREE);
  229.  
  230.     /* Remove sets of BB which are orthogonal to future expansions */
  231.     foreach_active_set(BB, last, p) {
  232. #ifndef HACK
  233.         if (! cdist0(p, praise))
  234. #else
  235.  {register int w,lastw;register unsigned int x;
  236. if((lastw=cube.inword)!=-1){x=p[lastw]&praise[lastw];if(~(x|x>>1)&cube.inmask)
  237. goto false;for(w=1;w<lastw;w++){x=p[w]&praise[w];if(~(x|x>>1)&DISJOINT)goto
  238. false;}}}{register int w,var,lastw;register pcube mask;for(var=cube.
  239. num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[var];lastw=
  240. cube.last_word[var];for(w=cube.first_word[var];w<=lastw;w++)if(p[w]&praise[w]&
  241. mask[w])goto nextvar;goto false;nextvar:;}}continue;
  242.  false:
  243. #endif
  244.             BB->active_count--, RESET(p, ACTIVE);
  245.     }
  246.  
  247.     /* Remove sets of CC which cannot be covered by future expansions */
  248.     foreach_remaining_set(CC, last, RAISE, p)
  249. #ifndef HACK
  250.         if (TESTP(p, ACTIVE) && ! setp_implies(p, praise)) {
  251. #else
  252.         if (TESTP(p, ACTIVE)) {
  253.             INLINEsetp_implies(p, praise, goto false1);
  254.             continue;
  255.         false1:
  256. #endif
  257.             CC->active_count--, RESET(p, ACTIVE);
  258.         }
  259. }
  260.  
  261.  
  262. /*
  263.     feasibly_covered -- determine if the cube represented by the cover
  264.     set c can be feasibly covered (i.e., if it is possible to raise all of
  265.     the necessary variables while still insuring orthogonality with R)
  266.  
  267.     General rule: if the raising cube would remain distance 1 or more
  268.     from each cube of the OFF-set, then the cubes is feasibly covered.
  269.     Equivalently, if any cube of the OFF-set becomes distance 0 to the
  270.     raising cube, then the cube is not feasibly covered.
  271. */
  272.  
  273. bool feasibly_covered(c)
  274. IN pset c;
  275. {
  276.     register pcube p, last, praise = set_or(cube.temp[2], RAISE, c);
  277.  
  278.     foreach_active_set(BB, last, p) {
  279. #ifndef HACK
  280.         if (cdist0(p, praise))
  281. #else
  282.  {register int w,lastw;register unsigned int x;
  283. if((lastw=cube.inword)!=-1){x=p[lastw]&praise[lastw];if(~(x|x>>1)&cube.inmask)
  284. goto false;for(w=1;w<lastw;w++){x=p[w]&praise[w];if(~(x|x>>1)&DISJOINT)goto
  285. false;}}}{register int w,var,lastw;register pcube mask;for(var=cube.
  286. num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[var];lastw=
  287. cube.last_word[var];for(w=cube.first_word[var];w<=lastw;w++)if(p[w]&praise[w]&
  288. mask[w])goto nextvar;goto false;nextvar:;}}
  289. #endif
  290.  
  291.             return FALSE;
  292.     false: ;
  293.     }
  294.     return TRUE;
  295. }
  296.  
  297.  
  298. /*
  299.     setup_BB_CC -- set up the blocking and covering set families;
  300.  
  301.     Note that the blocking family is merely the set of cubes of R, and
  302.     that CC is the set of cubes of F which might possibly be covered
  303.     (i.e., nonprime cubes, and cubes not already covered)
  304. */
  305.  
  306. void setup_BB_CC()
  307. {
  308.     register pcube p, last;
  309.  
  310.     /* Create the block and cover set families */
  311.     BB->active_count = BB->count;
  312.     foreach_set(BB, last, p)
  313.         SET(p, ACTIVE);
  314.  
  315.     CC->active_count = CC->count;
  316.     foreach_set(CC, last, p)
  317.         if (TESTP(p, COVERED) || TESTP(p, PRIME))
  318.             CC->active_count--, RESET(p, ACTIVE);
  319.         else
  320.             SET(p, ACTIVE);
  321. }
  322. /*
  323.     select_feasible -- Determine if there are cubes which can be covered,
  324.     and if so, raise those parts necessary to cover as many as possible.
  325. */
  326.  
  327. pcube select_feasible()
  328. {
  329.     register pcube p, last, bestfeas, *feas;
  330.     register int i, j;
  331.     int bestcover, bestsize;
  332.     int numfeas, *feas_covers, *feas_size;
  333.  
  334.     /* Find all of the feasibly covered cubes */
  335.     feas = (pcube *) alloc(CC->active_count * sizeof(pcube));
  336.     numfeas = 0;
  337.     foreach_remaining_set(CC, last, RAISE, p)
  338.         if (TESTP(p,ACTIVE))
  339.             if (setp_implies(p, RAISE)) {
  340.                 num_covered++;
  341.                 CC->active_count--;
  342.                 RESET(p, ACTIVE);
  343.                 SET(p, COVERED);
  344.             } else if (feasibly_covered(p))
  345.                 feas[numfeas++] = p;
  346.  
  347.     /* Exit here if there are no feasibly covered cubes */
  348.     if (numfeas == 0) {
  349.         mem_free((char *) feas);
  350.         return (pcube) NULL;
  351.     }
  352.  
  353.     /* Count how many other cubes each feasibly covered cube covers */
  354.     feas_covers = (int *) alloc(numfeas * sizeof(int));
  355.     feas_size = (int *) alloc(numfeas * sizeof(int));
  356.     for(i = 0; i < numfeas; i++) {
  357.         feas_covers[i] = 0;
  358.         feas_size[i] = set_ord(feas[i]);
  359.     }
  360.     for(i = 0; i < numfeas; i++)
  361.         for(j = 0; j < numfeas; j++)
  362.             if (setp_implies(feas[i], feas[j]))
  363.                 feas_covers[j]++;
  364.  
  365.     /* Select the smallest feasibly covered cube that covers the most cubes */
  366.     bestfeas = (pcube) NULL;
  367.     bestcover = bestsize = 0;
  368.     for(i = 0; i < numfeas; i++)
  369.         if (feas_covers[i] > bestcover) {
  370.             bestcover = feas_covers[i];
  371.             bestsize = feas_size[i];
  372.             bestfeas = feas[i];
  373.         } else if (feas_covers[i]==bestcover && feas_size[i]<bestsize) {
  374.             bestsize = feas_size[i];
  375.             bestfeas = feas[i];
  376.         }
  377.  
  378.     /* Add the necessary parts to the raising set, and see who we covered */
  379.     (void) set_or(RAISE, RAISE, bestfeas);
  380.     (void) set_diff(XFREE, XFREE, RAISE);
  381.     for(i = 0; i < numfeas; i++)
  382.         if (setp_implies(p=feas[i], RAISE)) {
  383.             num_covered++;
  384.             CC->active_count--;
  385.             RESET(p, ACTIVE);
  386.             SET(p, COVERED);
  387.         }
  388.     if (debug & EXPAND1)
  389.         printf("SELECT_FEASIBLE: can cover %d by covering %s\n",
  390.             bestcover, pc1(bestfeas));
  391.  
  392.     mem_free((char *) feas);
  393.     mem_free((char *) feas_covers);
  394.     mem_free((char *) feas_size);
  395.     return bestfeas;
  396. }
  397. /* 
  398.     most_frequent -- When all else fails, select a reasonable part to raise
  399.  
  400.     The active cubes of CC are the cubes which are covered by the
  401.     overexpanded cube of the original cube (however, we know that none
  402.     of them can actually be covered by a feasible expansion of the
  403.     original cube).  We resort to the MINI strategy of selecting to
  404.     raise the part which will cover the same part in the most cubes of
  405.     CC.
  406. */
  407.  
  408. int most_frequent()
  409. {
  410.     register int i, best_variable, best_count, *count;
  411.     register pset p, last;
  412.  
  413.     /* Count occurences of each variable */
  414.     count = (int *) alloc(cube.size * sizeof(int));
  415.     for(i = 0; i < cube.size; i++)
  416.         count[i] = 0;
  417.     foreach_remaining_set(CC, last, RAISE, p)
  418.         if (TESTP(p, ACTIVE))
  419.             set_adjcnt(p, count, 1);
  420.  
  421.     /* Now find which free part occurs most often */
  422.     best_count = best_variable = -1;
  423.     for(i = 0; i < cube.size; i++)
  424.         if (is_in_set(XFREE,i) && count[i] > best_count) {
  425.             best_variable = i;
  426.             best_count = count[i];
  427.         }
  428.     mem_free((char *) count);
  429.  
  430.     if (debug & EXPAND1)
  431.         printf("MOST_FREQUENT: %d is most frequent\n", best_variable);
  432.     return best_variable;
  433. }
  434. /*
  435.     mincov -- transform the problem of expanding a cube to a maximally-
  436.     large prime implicant into the problem of selecting a minimum
  437.     cardinality cover over a family of sets.
  438.  
  439.     When we get to this point, we must unravel the remaining off-set.
  440.     This may be painful.
  441. */
  442.  
  443. void mincov()
  444. {
  445.     int bound, expansion, nset, var, dist;
  446.     pset_family B;
  447.     register pcube xraise=cube.temp[1], xlower, p, last;
  448.  
  449.     /* Create B which are those cubes which we must avoid intersecting */
  450.     B = new_cover(BB->active_count);
  451.     foreach_active_set(BB, last, p)
  452.         (void) force_lower(set_copy(GETSET(B, B->count++),cube.emptyset),
  453.                             p, RAISE);
  454.  
  455.     /* Determine how many sets it will blow up into after the unravel */
  456.     nset = 0;
  457.     foreach_set(B, last, p) {
  458.         expansion = 1;
  459.         for(var = cube.num_binary_vars; var < cube.num_vars; var++)
  460.             if ((dist=set_dist(p, cube.var_mask[var])) > 1)
  461.                 expansion *= dist;
  462.         nset += expansion;
  463.         if (nset > 1000) {      /* oops, too many sets! */
  464.             sf_free(B);
  465.             set_insert(RAISE, most_frequent()); /* pick any part */
  466.             set_diff(XFREE, XFREE, RAISE);
  467.             (void) essen_parts();
  468.             return;
  469.         }
  470.     }
  471.  
  472.     /* Perform a containment to make it minimal */
  473.     B = unravel(B, cube.num_binary_vars);
  474.     foreach_set(B, last, p)
  475.         INLINEset_diff(p, cube.fullset, p);
  476.     B = sf_contain(B);
  477.     foreach_set(B, last, p)
  478.         INLINEset_diff(p, cube.fullset, p);
  479.     xlower = minimum_cover(B, &bound);
  480.     
  481.     /* Add lowered parts to the lowering set */
  482.     (void) set_or(LOWER, xlower, LOWER);
  483.  
  484.     /* Add any remaining free parts to the raising set */
  485.     (void) set_diff(xraise, XFREE, xlower);
  486.     (void) set_or(RAISE, xraise, RAISE);
  487.  
  488.     /* free set is now empty */
  489.     (void) set_copy(XFREE, cube.emptyset);
  490.     BB->active_count = 0;
  491.  
  492.     if (debug & EXPAND1)
  493.         printf("MINCOV: lower=%s, raise=%s\n", pc1(xlower), pc2(xraise));
  494.     sf_free(B);
  495.     set_free(xlower);
  496. }
  497. pcover mini_order(F, compare)
  498. pcover F;
  499. int (*compare)();
  500. {
  501.     register int *count, cnt, n = cube.size, i;
  502.     register pcube p, last;
  503.     pcube *F1;
  504.  
  505.     /* Perform a column sum over the set family */
  506.     count = sf_count(F);
  507.  
  508.     /* weight is "inner product of the cube and the column sums" */
  509.     foreach_set(F, last, p) {
  510.         cnt = 0;
  511.         for(i = 0; i < n; i++)
  512.             if (is_in_set(p, i))
  513.                 cnt += count[i];
  514.         PUTSIZE(p, cnt);
  515.     }
  516.  
  517.     mem_free((char *) count);
  518.     qsort((char *) (F1 = sf_list(F)), F->count, sizeof(pcube), compare);
  519.     F = sf_unlist(F1, F->count, F->sf_size);
  520.     return F;
  521. }
  522.